/* 堆排序 */

#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<thread>
using namespace std;

constexpr int N = 14;
constexpr int WIDTH = 4;

int log2(int n)
{
	int mask = 0xfffffffe;
	int res = 0;

	n &= mask;
	while (0 != n)
	{
		res++;
		mask <<= 1;
		n &= mask;
	}
	return res;
}

void PrintHeapData(int *data, int count)
{
	system("clear");

	int level = log2(count) + 1;
	int idx = 0;

	int nIndexPerLevel = 0;
	for (int i = 0; i < level; i++)
	{
		nIndexPerLevel = nIndexPerLevel * 2 + 1;
		nIndexPerLevel = min(nIndexPerLevel, count);
		int width = WIDTH * (int)pow(2, level - i - 1);
		int spaceNum = width / 2 - 2;

		if (spaceNum > 0)
		{
			cout << setw(spaceNum) << ' ';
		}

		while (idx < nIndexPerLevel)
		{	
			cout << setiosflags(ios::left) << setw(width) << data[idx];
			idx++;
		}
		cout << endl;
	}

	this_thread::sleep_for(1s);
}

void AdjustNode(int *data, int idx, int count)
{
	int i = idx;
	int t = data[i];

	while (i < count / 2)
	{
 		int leafIdx = 2 * i + 1;

		if (2 * i + 2 < count && data[2 * i + 2] > data[leafIdx])
		{
			leafIdx = 2 * i + 2;
		}

		if (t < data[leafIdx])
		{
			//data[i] = data[leafIdx];
			//其实这里不用swap，只要像上面这行，data[i] = data[leafIdx]一样即可
			//此处为了演示直观，使用swap
			swap(data[i], data[leafIdx]);
			i = leafIdx;
			PrintHeapData(data, N);
		}
		else
		{
			break;
		}
	}

	/*
	if (i != idx)
	{
		data[i] = t;
		PrintHeapData(data, N);
	}
	*/
}

int main(void)
{
	int data[]{ 99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92 };
	PrintHeapData(data, N);

	system("clear");
	cout << "开始构建最大堆：\n";
	this_thread::sleep_for(1s);
	int firstLeafIdx = N / 2;	//第一个叶子节点
	//构建最大堆
	for (int i = firstLeafIdx - 1; i >= 0; i--)
	{
		AdjustNode(data, i, N);
	}

	system("clear");
	cout << "现在开始排序：\n";
	this_thread::sleep_for(1s);

	PrintHeapData(data, N);

	for (int i = 0; i < N - 1; i++)	//N个数，只要排序N - 1次就够了
	{
		//因为是最大堆，现在data[0]就是最大值
		swap(data[0], data[N - 1 - i]);
		PrintHeapData(data, N);

		AdjustNode(data, 0, N - 1 - i);
	}

	return 0;
}
